Andrea Lincoln
https://andrealincoln.github.io/
I am a faculty at Boston University in the computer science department. I am teaching CS 330 this fall. I will be starting Algorithms Advice at BU this fall. I graduated from my PhD at MIT in 2020. I was fortunate to be advised by Virginia Vassilevska Williams.
My publications, primarily in fine-grained complexity are listed below. I also worked on the Residual Stream Viewer, a tool to help interpret the residual stream of GPT2-small. You can check it out here. If you want to watch a youtube tutorial it exists here.
I hope to build and refine theoretical models that crystallize concerns about complex systems. I strive to build networks of reductions that give shared explanations for the hardness of problems.
Research Interests: Fine Grained Complexity, Average-Case Complexity, Lower Bounds, Algorithms.
The Complexity of Average-Case Dynamic Subgraph Counting
Monika Henzinger, Andrea Lincoln, Barna Saha
SODA 2022
How Compression and Approximation Affect Efficiency in String Distance Measures
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha
SODA 2022
New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
FOCS 2020
Faster Random k-CNF Satisfiability
Andrea Lincoln, Adam Yedidia
ICALP 2020 [Invited to special issue of Theory of Computing Systems]
Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis
Michael Bender, Rezaul Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan Liu, Jayson Lynch, Helen Xu
SPAA 2020
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs
Andrea Lincoln and Nikhil Vyas
ITCS 2020
Monochromatic triangles, intermediate matrix products, and convolutions
Andrea Lincoln, Adam Polak and, Virginia Vassilevska Williams
ITCS 2020, short presentation at HALG'20
Public-Key Cryptography: in the Fine-Grained Setting
Rio LaVigne, Andrea Lincoln, Virginia Vassilevska Williams
CRYPTO 2019
Cache-Adaptive Exploration: Experimental Results and Scan-Hiding for Adaptivity
Andrea Lincoln, Quanquan Liu, Jayson Lynch, Helen Xu
SPAA 2018
Erik Demaine, Andrea Lincoln, Quanquan Liu, Jayson Lynch, Virginia Vassilevska Williams
ITCS 2018
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Andrea Lincoln, Virginia Vassilevska Williams, and Ryan R. Williams
SODA 2018
Conditional Hardness for Sensitivity Problems
Monika Henzinger, Andrea Lincoln, Stefan Neumann and Virginia Vassilevska Williams
ITCS 2017
Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes,...
Erik D Demaine, Martin L Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, Y William Yu
Journal of Information Processing 2017
Deterministic Time-Space Tradeoffs for k-SUM,
A. Lincoln, V. Vassilevska Williams, J. R. Wang and R. R. Williams,
ICALP 2016
Michael Bender, Erik Demaine, Roozbeh Ebrahimi, Jeremy Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch and Samuel Mccauley.
SPAA 2016; HALG 2017
The one-out-of-k retrieval problem and Linear Network Coding,
Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln and Muriel Medard,